#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) return false;
        int m = matrix.size(), n = matrix[0].size();

        int x = m - 1, y = 0;
        while (x >= 0 && y < n) {
            if (matrix[x][y] < target) {
                y++;
            }
            else if (matrix[x][y] > target) {
                x--;
            }
            else return true;
        }
        return false;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0, n = nums.size();
        for (int i = 0; i <= n; i++) {
            if (i < n)
                ret ^= nums[i];
            ret ^= i;
        }
        return ret;
    }
};

class Solution {
public:
    bool sameTree(TreeNode* t1, TreeNode* t2)
    {
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        if (t1->val != t2->val) return false;
        return sameTree(t1->left, t2->left) && sameTree(t1->right, t2->right);
    }

    bool checkSubTree(TreeNode* t1, TreeNode* t2)
    {
        if (t1 == nullptr) return false;
        if (sameTree(t1, t2)) return true;
        return checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2);
    }
};

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
public:
    void dfs(TreeNode* root, int sum, int target)
    {
        if (root == nullptr) return;

        sum += root->val;
        path.push_back(root->val);

        if (sum == target) ret.push_back(path);

        dfs(root->left, sum, target);
        dfs(root->right, sum, target);
        path.pop_back();
    }

    int pathSum(TreeNode* root, int sum)
    {
        if (root == nullptr) return 0;

        dfs(root, 0, sum);
        pathSum(root->left, sum);
        pathSum(root->right, sum);

        return ret.size();
    }
};